\section{System Description} 
\label{sec:system_description}

For the P2P overlay network, we use the Pastry implementation, FreePastry. When a peer wants to join the pastry ring he gets a pastry ID which is also his Player ID.

A peer in the pastry ring must be running our implementation of a FreePastry Application, LudoApp, in order to participate in a Ludo game. Consequently, the peer can also be selected as operator (OP) for another game. A peer, Alice, wanting to play can request another known peer, Bob, for a game. Bob will now be able to initiate the game. Consecutively, if Alice gets a game request, she will forward the request to Bob. At some point after Bob has received one or more game requests, he may want to start the game. He then initiates the game by calculating a Game ID, which is a function of all the participating player's IDs:

\begin{displaymath}
      GameID = XOR(PlayerID_{1}, PlayerID_{2}, ..., PlayerID_{k})
 \end{displaymath}
  
By choosing XOR as our function we make sure that the resulting Game ID is dependent on every single player's ID.

To manage the game, a number of OPs are selected. This is done by first calculating a number of OP IDs from the Game ID:

\begin{displaymath}
     OpID_{i} = h(GameID+i),
 \end{displaymath}
  
where the function h is a random hash function with uniform output. $ OP_{i} $ is then the peer with ID closest to $ OpID_{i} $.

\begin{figure}[h!t]
\begin{center}
\includegraphics[scale=0.75]{initgame.eps}
\caption{\textit{Game initiation}}
\label{initgame}
\end{center}
\end{figure}

The OPs jointly roll the dice before a player's move: each OP makes a random seed part, and the resulting parts are combined (using XOR) and used as a seed for the next dice roll. However, if the OPs were to exchange their part of the seed in plain text, it would allow an adversarial OP to wait until he has received the other seed parts and chose his part such that he can decide the resulting dice roll. To solve this, we let all OPs calculate a cryptographically secure one-way hash of their seed part and first distribute the hash instead.


When an OP has received all hash values, it sends its seed part to all other OPs. When all seed parts are received, the combined seed value is computed and the dice is rolled.

\begin{figure}[h!t]
\begin{center}
\includegraphics[scale=0.75]{gameplay1.eps}
\caption{\textit{Player sends move, OPs calculate next dice}}
\label{gameplay1}
\end{center}
\end{figure}

The resulting game state (consisting of the dice, the board configuration and the player in turn) is sent from every OP to every player, meaning that with $ n $ OPs, each player will receive $ n $ game states. 

We now assume that at least  $ k $ of the $ n $  OPs are trustworthy, where $ k > n/2 $, and hence send out the same state. We call this the majority state, perhaps misusing the term majority a bit. In our implementation, $ k = 3 $ and $ n = 5 $. A player can now safely select the majority state.

\begin{figure}[h!t]
\begin{center}
\includegraphics[scale=0.75]{gameplay2.eps}
\caption{\textit{OPs send new state to players, players select majority state}}
\label{gameplay2}
\end{center}
\end{figure}

After updating the game state, the player in turn sends his move to all OPs. If an OP considers the move to be valid, it will once again initiate the calculation of the dice, and the game progresses.

